package nachos.threads;

import nachos.machine.*;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * 根据线程优先级选择线程的调度程序
 *
 * <p>
 * 优先级调度程序将优先级与每个线程相关联
 * 从列中移出的线程总是优先级不低于其他正在等待的线程的优先级
 * 与循环调度程序一样，从队中移出的线程总是具有相同（最高）优先级的所有线程中等待时间最长的线程
 *
 * <p>
 * 本质上，优先级调度程序以循环方式向所有优先级最高的线程提供访问权限，而忽略所有其他线程
 * 如果总是有一个线程以更高的优先级等待，那么这有可能导致线程饥饿
 *
 * <p>
 * 优先级调度器必须部分解决优先级反转问题
 * 特别是，优先级必须通过锁和 join 来提供
 */
public class PriorityScheduler extends Scheduler {
    /**
     * 分配一个新的优先级调度程序
     */
    public PriorityScheduler() {
    }

    /**
     * 分配一个新的优先级线程队列
     *
     * @param transferPriority true 如果此队列应将优先级从等待线程转移到拥有线程
     * @return 一个新的优先级线程队列
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
        return new PriorityQueue(transferPriority);
    }

    public int getPriority(KThread thread) {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getPriority();
    }

    public int getEffectivePriority(KThread thread) {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getEffectivePriority();
    }

    public void setPriority(KThread thread, int priority) {
        Lib.assertTrue(Machine.interrupt().disabled());

        Lib.assertTrue(priority >= priorityMinimum &&
                priority <= priorityMaximum);

        getThreadState(thread).setPriority(priority);
    }

    public boolean increasePriority() {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMaximum)
            return false;

        setPriority(thread, priority + 1);

        Machine.interrupt().restore(intStatus);
        return true;
    }

    public boolean decreasePriority() {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMinimum)
            return false;

        setPriority(thread, priority - 1);

        Machine.interrupt().restore(intStatus);
        return true;
    }

    /**
     * 新线程的默认优先级，不要更改此值
     */
    public static final int priorityDefault = 1;
    /**
     * 线程可以具有的最低优先级，不要更改此值
     */
    public static final int priorityMinimum = 0;
    /**
     * 线程可以具有的最高优先级，不要更改此值
     */
    public static final int priorityMaximum = 7;

    /**
     * 返回指定线程的调度状态
     *
     * @param thread 要返回其调度状态的线程
     * @return 指定线程的调度状态
     */
    protected ThreadState getThreadState(KThread thread) {
        if (thread.schedulingState == null)
            thread.schedulingState = new ThreadState(thread);

        return (ThreadState) thread.schedulingState;
    }

    /**
     * 按优先级对线程进行排序的线程队列
     */
    protected class PriorityQueue extends ThreadQueue {
        PriorityQueue(boolean transferPriority) {
            this.transferPriority = transferPriority;
        }

        public void waitForAccess(KThread thread) {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).waitForAccess(this);
        }

        public void acquire(KThread thread) {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).acquire(this);
        }

        public KThread nextThread() {
            Lib.assertTrue(Machine.interrupt().disabled());

            ThreadState threadState = pickNextThread();
            if (threadState == null) {
                return null;
            }

            // 将该线程移除后返回
            list.remove(threadState);
            return threadState.thread;
        }

        /**
         * 返回 nextThread() 将返回的线程，而不修改此队列的状态
         *
         * @return nextThread() 将返回的线程
         */
        protected ThreadState pickNextThread() {
            ThreadState nextThreadState = null;

            // 当前最大优先级
            int currentMaxPriority = -1;

            // 遍历优先级队列中的每一个线程
            for (ThreadState threadState : list) {
                // 根据是否可以传递优先级，获取到实际用于比较的优先级
                int threadPriority;
                if (transferPriority) {
                    // 线程包括其等待队列中最高的优先级
                    threadPriority = threadState.getEffectivePriority();
                } else {
                    // 线程本身的优先级（未传递）
                    threadPriority = threadState.getPriority();
                }

                // 选择优先级更高的线程
                if (threadPriority > currentMaxPriority) {
                    nextThreadState = threadState;
                    currentMaxPriority = threadPriority;
                }
            }

            if (list.size() != 0) {
                // 将保存的有效优先级设置为有效
                KThread.setPriorityStatus(true);
            }


            return nextThreadState;
        }

        public void print() {
            Lib.assertTrue(Machine.interrupt().disabled());

            // 打印所有线程
            for (Iterator i = list.iterator(); i.hasNext(); ) {
                System.out.print(i.next() + " ");
            }
        }

        /**
         * true 如果此队列应将优先级从等待线程转移到拥有此队列的线程
         */
        public boolean transferPriority;

        // 优先级队列中的线程列表
        protected LinkedList<ThreadState> list = new LinkedList<>();
    }

    /**
     * 线程的调度状态
     * 这应该包括线程的优先级、有效优先级、它拥有的任何对象以及它等待的队列（如果有的话）
     *
     * @see nachos.threads.KThread#schedulingState
     */
    protected class ThreadState {
        /**
         * 分配一个新的 ThreadState 对象并将其与指定的线程关联
         *
         * @param thread 此状态所属的线程
         */
        public ThreadState(KThread thread) {
            this.thread = thread;

            setPriority(priorityDefault);

            // 设置有效优先级
            this.effectivePriority = this.priority;
        }

        /**
         * 返回关联线程的优先级
         *
         * @return 关联线程的优先级
         */
        public int getPriority() {
            return priority;
        }

        /**
         * 返回关联线程的有效优先级
         *
         * @return 关联线程的有效优先级
         */
        public int getEffectivePriority() {
            // 尝试使用之前保存的数据
            if (KThread.getPriorityStatus()) {
                return effectivePriority;
            }

            // 重新计算有效优先级
            effectivePriority = priority;

            // 遍历该线程的等待线程列表
            for (KThread waitThread : thread.getWaitThreadList()) {
                // 等待线程的有效优先级
                int targetPriority = getThreadState(waitThread).getEffectivePriority();
                // 如果等待线程的有效优先级更高
                if (effectivePriority < targetPriority) {
                    // 进行优先级传递
                    effectivePriority = targetPriority;
                }
            }

            return effectivePriority;
        }

        /**
         * 将关联线程的优先级设置为指定值
         *
         * @param priority 新的优先级
         */
        public void setPriority(int priority) {
            if (this.priority == priority)
                return;

            // 如果设置的优先级在有效范围值之外的话，打印信息并返回
            if (priority < priorityMinimum || priority > priorityMaximum) {
                System.out.println("优先级设置失败");
                return;
            }

            // 将保存的有效优先级设置为无效
            KThread.setPriorityStatus(false);

            this.priority = priority;
        }

        /**
         * 在指定优先级队列使用 waitForAccess(thread)（thread 是关联的线程）时调用
         * 因此，关联线程正在等待访问由 waitQueue 保护的资源
         * 仅当关联线程无法立即获得访问权限时，才会调用此方法
         *
         * @param waitQueue 关联线程现在正在等待的队列
         * @see nachos.threads.ThreadQueue#waitForAccess
         */
        public void waitForAccess(PriorityQueue waitQueue) {
            Lib.assertTrue(Machine.interrupt().disabled());

            // 将线程加入优先级队列中去
            waitQueue.list.add(this);
        }

        /**
         * 当关联线程已获得对由 waitQueue 保护的内容的访问权限时调用
         * 这可能是由于在 waitQueue 上调用 acquire(thread)，或者在 waitQueue 上调用 nextThread()
         *
         * @see nachos.threads.ThreadQueue#acquire
         * @see nachos.threads.ThreadQueue#nextThread
         */
        public void acquire(PriorityQueue waitQueue) {
            Lib.assertTrue(Machine.interrupt().disabled());

            // 断言此时优先级队列中内容为空
            Lib.assertTrue(waitQueue.list.isEmpty());
        }

        /**
         * 与此对象关联的线程
         */
        protected KThread thread;
        /**
         * 关联线程的优先级
         */
        protected int priority;

        // 有效优先级
        protected int effectivePriority;
    }
}
